#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    /**
     * @brief 
     * 首先我们取出所有不为破折号的字符，题目要求对取出的字符进行重新分组，
     * 使得每个分组恰好包含 kk 个字符，且必须满足第一个分组包含的字符个数必须小于等于 kk，
     * 但至少要包含 11 个字符。设已经取出的字符的总数为 nn，
     * 只需满足第一个分组包含的字符数目刚好等于 n \bmod knmodk，剩余的分组包含的字符数目刚好等于 kk。
     * 我们可以从字符串 ss 的末尾开始往前取出字符构建新的字符串 \textit{ans}ans。
     * 每次取出字符时首先判断该字符是否为破折号，如果为破折号则跳过；否则将当前的字符计数 \textit{cnt}cnt 加 11，同
     * 时检查如果当前字符为小写字母则将其转化为大写字母，将当前字符加入到字符串 \textit{ans}ans 的末尾。
     * 对字符进行计数时，每隔 kk 个字符就在字符串 \textit{ans}ans 中添加一个破折号。
     * 特殊情况需要处理，字符串 \textit{ans}ans 的最后一个字符为破折号则将其去掉。
     * 我们对已经构建的字符串 \textit{ans}ans 进行反转即为返回结果
     * 
     * @param s 
     * @param k 
     * @return string 
     */
    string licenseKeyFormatting(string s, int k)
    {
        string ans;
        int cnt = 0, sLen = s.size();

        for (int i = sLen - 1; i >= 0; i--)
        {
            if (s[i] != '-')
            {
                ans.push_back(toupper(s[i]));
                cnt++;
                if (cnt % k == 0)
                {
                    ans.push_back('-');
                }
            }
        }
        // which could be shorter than k but still must contain at least one character.
        if (sLen > 0 && ans.back() == '-')
        {
            ans.pop_back();
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};
int main()
{
    Solution s;
    cout << s.licenseKeyFormatting("5F3Z-2e-9-w", 4) << endl;
    return 0;
}
